#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100

typedef int VertexType;
typedef int EdgeType;

typedef struct {
	VertexType vexs[MAXVEX];
	EdgeType arc[MAXVEX][MAXVEX];
	int numVertexes, numEdges, numColors;
}MGraph;

int colorSum = 0;  // 可用方案总数
int x[MAXVEX];  // 存储方案，第i个结点颜色
void graph_create(MGraph* G);
int ok(int layer, MGraph* G);
void backtrack(int layer, MGraph* G);

int main(int argc, char const* argv[]) {
	MGraph* G = (MGraph*)malloc(sizeof(MGraph));
	graph_create(G);
	backtrack(1, G);
	printf("all strateges: %d\n", colorSum);
}

void graph_create(MGraph* G) {
	int i, j, k;
	printf("enter numVertexes, numEdges and numColors: ");
	scanf("%d %d %d", &G->numVertexes, &G->numEdges, &G->numColors);
	printf("vexs[]: ");
	for (k = 0; k < G->numVertexes; ++k)
		scanf("%d", &G->vexs[k]);
	// init
	for (i = 0; i < G->numVertexes; ++i)
		for (j = 0; j < G->numVertexes; ++j)
			G->arc[i][j] = 0;

	printf("build related nodes: \n");
	for (k = 0; k < G->numEdges; ++k) {
		printf("%dth (vi, vj): ", k);
		scanf("%d %d", &i, &j);
		G->arc[i][j] = 1;  // 1号结点为开始结点
		G->arc[j][i] = G->arc[i][j];  // 无向图邻接矩阵对称
	}
}

int ok(int layer, MGraph* G) {
	int i;
	for (i = 1; i < layer; ++i) 
		if (G->arc[layer][i] == 1 && x[layer] == x[i])
			return 0;
	return 1;
}

void backtrack(int layer, MGraph* G) {
	int i;
	if (layer > G->numVertexes) {
		++colorSum;
		for (i = 1; i <= G->numVertexes; ++i)
			printf("%d ", x[i]);
		printf("\n");
		return ;
	}

	for (i = 1; i <= G->numColors; ++i) {
		x[layer] = i;
		if (ok(layer, G) == 1)
			backtrack(layer+1, G);
		x[layer] = 0; 
	}
}